1921G - Mischievous Shooter - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

void run() {
	int n, m, k; cin >> n >> m >> k;

	vector a(min(n, m), vector<int>(max(n, m)));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			char c; cin >> c;
			if (n <= m) a[i][j] += c == '#';
			else a[j][i] += c == '#';
		}
	}
	if (n > m) swap(n, m);

	for (auto& v : a) {
		for (int i = 1; i < m; i++) {
			v[i] += v[i - 1];
		}
	}

	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int cur = 0;
			for (int l = 0; l <= k and i + l < n; l++) {
				cur += a[i + l][min(j + k - l, m - 1)] - (j ? a[i + l][j - 1] : 0);
			}
			ans = max(ans, cur);

			cur = 0;
			for (int l = 0; l <= k and i - l >= 0; l++) {
				cur += a[i - l][min(j + k - l, m - 1)] - (j ? a[i - l][j - 1] : 0);
			}
			ans = max(ans, cur);

			cur = 0;
			for (int l = 0; l <= k and i + l < n; l++) {
				cur += a[i + l][j] - (j - k + l > 0 ? a[i + l][j - k + l - 1] : 0);
			}
			ans = max(ans, cur);

			cur = 0;
			for (int l = 0; l <= k and i - l >= 0; l++) {
				cur += a[i - l][j] - (j - k + l > 0 ? a[i - l][j - k + l - 1] : 0);
			}
			ans = max(ans, cur);
		}
	}

	cout << ans << '\n';
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int t; cin >> t; while (t--) run();
}